Les données sont stockées dans un fichier csv téléchargeable : fichier csv à télécharger

Voici un aperçu des données :

Voici une représentation de ces données :

Nous introduisons une nouvelle donnée (appelée cible dans notre exemple) avec ses deux caractéristiques : une force de 12 et un courage de 12,5 . Le but de l'algorithme KNN des $k$ plus proches voisins est de déterminer le type de cette nouvelle donnée.

1. Dans un premier, il faut fixer le nombre de voisins. Nous allons choisir $k$=7.

   Voici une nouvelle représentation avec la cible et la recherche des 7 voisins les plus proches proches, ceux qui se trouvent dans le cercle bleu :

   

   En utilisant les voisins de type "chevalier" et de type "fantassin", déterminer le type le plus probable de notre cible.

2. On considère désormais la valeur $=13$. Voici une nouvelle représentation avec la cible et la recherche des 13 voisins les plus proches proches, ceux qui se trouvent dans le cercle bleu : Déterminer le type le plus probable de notre cible dans ce cas ?

Nous reprenons le même ensemble de données :

Nous introduisons une cible : force = 5 et courage = 12,5

1. On choisit $k$=4 et la distance schématisée par un disque .

   

   1. Quel est le type de notre donnée cible ? Quel est le problème ?

   2. Donner une valeur de $k$ qui permette de décider du type de notre donnée cible ?

   3. Donner pour cette valeur de $k$ le type de la donnée cible.

2. On choisit $k=9$. Pour la distance, on décide que les valeurs de la force n'ont pas d'importance. La distance dépend du courage.

   

   Quel est le type de notre donnée cible ?

3. On choisit $k=5$. Pour la distance, on décide que les valeurs du courage n'ont pas d'importance. La distance dépend de la force.

   

   Quel est le type de notre donnée cible ?

1. 1. Tester le script Python suivant :

      from math import *
      import matplotlib.pyplot as plt
      
      # Données de type 1
      liste_x_1=[1,3,8,13]
      liste_y_1=[28,27.2,37.6,40.7]
      
      # Données de type 2
      liste_x_2=[2,3,10,15]
      liste_y_2=[30,26,39,35.5]
      
      plt.axis([0,15, 0, 50]) # Attention [x1,x2,y1,y2]
      plt.xlabel('Caractéristique 1')                     # premier commentaire attendu
      plt.ylabel('Caractéristique 2')
      plt.title('Représentation des deux types')
      plt.axis('equal') # Pour avoir un repère orthonormé
      plt.grid()
      plt.scatter(liste_x_1,liste_y_1, label='type 1')    # second commentaire attendu
      plt.scatter(liste_x_2,liste_y_2, label='type 2')
      plt.legend()
      plt.show()
      

   2. Remplacer les deux commentaires attendus par un commentaire expliquant le rôle des fonctions plt.label et plt.scatter.

2. 1. Vous pouvez ajouter des formes (rectangle, ellipse, etc.).

      Exécuter le script suivant :

      from math import *
      import matplotlib.pyplot as plt
      
      # Données de type 1
      liste_x_1=[1,3,8,13]
      liste_y_1=[28,27.2,37.6,40.7]
      
      # Données de type 2
      liste_x_2=[2,3,10,15]
      liste_y_2=[30,26,39,35.5]
      
      fig, ax = plt.subplots()
      
      plt.axis([0,15, 0, 50]) # Attention [x1,x2,y1,y2]
      plt.xlabel('Caractéristique 1')
      plt.ylabel('Caractéristique 2')
      plt.title('Représentation des deux types')
      plt.axis('equal') # pour avoir un repère orthonormé. Faire des tests.
      plt.grid()
      plt.scatter(liste_x_1,liste_y_1, label='type 1')
      plt.scatter(liste_x_2,liste_y_2, label='type 2')
      plt.legend()
      
      # Ajout d'un cercle (ou d'une ellipse)
      ax.add_artist(plt.Circle((6, 30), 4, edgecolor='b', facecolor='none'))
      
      # Ajout d'un rectangle
      ax.add_artist(
          plt.Rectangle((6,0), 2, 50,
                            edgecolor = 'black', facecolor = 'none',
                            fill = True, hatch = '/', linestyle = 'dashed',
                            linewidth = 3, zorder = 1))
      
      plt.show()
      

   2. Quel est le rôle du premier argument (6, 30) de la fonction plt.Circle ?

   3. Quel est le rôle des trois premiers arguments (6,0), 2 et 50 de la fonction plt.Rectangle ?

Sur un champ de bataille de la Première Guerre Mondiale un mémorial a été construit. Afin de réaliser une extension, des fouilles préventives ont été réalisées par l'INRAP (Institut National de Recherches Archéologiques Préventives).
Au cours de ces fouilles, différents objets ou éléments de squelettes humains ont été trouvés. L'étude de ces découvertes a permis d'identifier la nationalité de nombreux artéfacts retrouvés : soit allemand, anglais ou français.
Le plan ci-dessous représente la zone de fouille et la position des éléments dont l'origine a été identifiée. L'unité est le mètre.

Un élément d'un squelette a été retrouvé en $(10;4)$ ; il est représenté par un losange couleur magenta sur le plan.
L'objectif est de déterminer une origine probable pour cet élément de squelette avant de le déposer dans un ossuaire.

La distance qui sera prise en compte est la distance dite de Tchebychev. (la définition précise de celle-ci sera donnée au 2.)
Ce que vous devez seulement savoir sur cette distance pour cet exercice c'est que l'ensemble des points se trouvt à une distance $r$ d'un point $I$ correspond au pourtour du carré, de centre $I$, de côtés parallèles aux axes et de longueurs $2r$.
Sur le graphique ci-dessus, le carré dessiné :

• en rouge correspond ainsi à l'ensemble des points se trouvant à 3 mètres.

• en noir correspond ainsi à l'ensemble des points se trouvant à 1 mètre.

1. 1. À quelle valeur de $k$ correspond le carré noir ?

   2. Quelle serait l'origine de l'élément de squelette en considérant cette valeur de $k$ ?

2. On choisit $k=9$. Quelle serait l'origine de l'élément de squelette en considérant cette valeur de $k$ ?

3. On choisit $k=11$. Quelle serait l'origine de l'élément de squelette en considérant cette valeur de $k$ ?

4. Peut-on savoir à coup sûr, en prenant une valeur de $k$ inférieure au égale à 11, si le combattant dont on a trouvé un élément de squelette était un combattant de la Triple-Entente (France + Royaume-Uni + Russie) ou de la Triple-Alliance (Allemagne + Autriche-Hongrie + Italie) ?

On conidère le code ci-dessous.

from math import *
# from random import *
import matplotlib.pyplot as plt
# import numpy as np
# from scipy.stats import linregress

# Données de type 1
liste_x_1=[1,3,8,13]
liste_y_1=[28,27.2,37.6,40.7]

# Données de type 2
liste_x_2=[2,3,10,15]
liste_y_2=[30,26,39,35.5]

plt.axis([0,15, 0, 50]) # Attention [x1,x2,y1,y2]
plt.axis('equal')
plt.xlabel('Caractéristique 1')
plt.ylabel('Caractérstique 2')
plt.title('Représentation des deux types')
plt.grid()
plt.scatter(liste_x_1,liste_y_1, label='type 1')
plt.scatter(liste_x_2,liste_y_2, label='type 2')

plt.scatter(7,28.4, label='cible')
plt.legend()
plt.show()

table = [['t1',1,28], ['t1',3,27.2], ['t1',8,37.6], ['t1',13,40.7], ['t2',2,30], ['t2',3,26], ['t2',10,39], ['t2',15,35.5]]
cible = [7,28.4]
k=3

def k_plus_proches_voisins(table, cible, k) :
    """Revoie la liste des k plus proches voisins de la cible"""
    
    
    def distance_cible(donnee) :
        """ renvoie la distance entre la donnée et la cible, on choisit la distance de Manhattan"""
        
        distance = abs(donnee[1]-cible[0])+abs(donnee[2]-cible[1])
        
        return distance
    
    table_triee = sorted(table, key = distance_cible)
    
    proches_voisins = []
    
    for i in range(k) : 
        proches_voisins.append(table_triee[i])
        
    return proches_voisins

print("La liste des ",k," plus proches voisins de la cible : ",k_plus_proches_voisins(table,cible,k))

Vous pouvez exécuter ce code directement sur ce trinket.

1. Afficher le résultat de la fonction k_plus_proches_voisins(table,cible,k). Quel est le type de la cible ?

2. Quelle est la valeur de $k$ ?

3. Quelle distance a-t-on utilisée ?

4. Utiliser d'autres valeurs de $k$. Quel est l'effet sur le type de la cible ?

5. Changer la distance. Programmer la distance de Tchebychev. Quel est l'effet sur le type de la cible ?

Le but est d'étudier plus en détail l'exemple qui a servi d'introduction visuelle à l'algorithme des $k$ plus proches voisins.

1. Voici une fonction impor :

   import csv
   def impor(nom):
       lecteur = csv.DictReader(open(nom + '.csv' , "r", encoding='utf-8-sig' ) , delimiter = ";")
       return [ligne for ligne in lecteur]
   

   Expliquer comment utiliser cette fonction afin de récupérer dans une variable nommée combattants la liste des personnages associés à leur force, courage et type ; données initialement dans un fichier personnages.csv accessible ici directement.

2. Proposer une fonction est_personnage qui prend en paramètres une liste de personnages comme celle renvoyée par la fonction de la question précédente et un nom sous forme de chaîne de caractères. Cette fonction renvoie un booléen donnant l'appartenance ou non d'un personnage portant le nom donné comme argument dans cette liste.

   Utiliser cette fonction afin de savoir s'il existe un combattant du nom de "Lis" ?

3. Trier la table des personnages par le type.

   Vous pouvez utiliser la lambda-fonction lambda x: x["Type"] comme vu dans le cours sur le tri d'une table.

4. Écrire et utiliser l'algorithme des $k$ plus proches voisins avec $k=7$ et la distance euclidienne pour savoir quel sera le type du personnage nommé "popsi", de force 12 et de courage 12.5 selon la table des personnages connus.

À l’entrée à l’école de Poudlard, le Choixpeau magique répartit les élèves dans les différentes maisons (Gryffondor, Serpentard, Serdaigle et Poufsouffle) en fonction de leur courage, leur loyauté, leur sagesse et leur malice.

Le Choixpeau magique dispose d’un fichier CSV dans lequel sont répertoriées les données d’un échantillon d’élèves. Le fichier ChoixpeauMagique.csv est téléchargeable à cet endroit : choixpeauMagique.csv

On souhaite que Choixpeau magique oriente :

On décompose l'exercice en 5 parties :

1. Modéliser un élève

   On modélise un élève par un dictionnaire.
   Exemple : {'Nom': 'Bellatrix', 'Courage': 10, 'Loyauté': 4, 'Sagesse': 9, 'Malice': 9, 'Maison': 'Serpentard'}

   1. Donner la modélisation de l'élève Anthony.

   2. On utilise la distance de Manhattan.

      1. Vérifier à la main que la distance entre Hermione et Adrian est égale à 8.

      2. Quelle est la distance entre Angelina et Drago ?

      3. Écrire le code d'une fonction distance qui prend deux élèves en paramètre et qui renvoie la distance entre ces deux élèves. Ne pas oublier de préciser la documentation et donner au moins un test.

   Code de déblocage de la correction :

2. Charger les données de la table

   Se reporter au chapitre sur les tables afin d'écrire une fonction qui permet de récupérer les données des élèves d'un fichier CSV pour les stocker dans une liste. On doit obtenir une liste de dictionnaires.

   Code de déblocage de la correction :

3. Trouver la maison majoritaire

   1. Écrire une fonction frequence_des_maisons(table) qui prend en paramètre une table d'élèves et qui renvoie le dictionnaire des fréquences des maisons. Vous devez obtenir : {'Serpentar': 12, 'Gryffondor': 17, 'Serdaigle': 11, 'Poufsouffle': 10}.

   2. Écrire une fonction maison_majoritaire(table) qui prend en paramètre une table d'élèves et qui renvoie le nom de la maison la plus représentée.

   Code de déblocage de la correction :

4. Algorithme des 7 plus proches voisins

   On dispose d'une table et d'une nouvelle élève Niue qui n'a pas encore de maison. On sait que cette élève est de "Courage" de niveau 7, de "Loyauté" de niveau 8, 5 en niveau de "Sagesse" et 4 en niveau de "Malice".
   On cherche les 7 plus proches voisins de ce nouveau.

   1. Écrire l'algorithme des 7 plus proches voisins.

   2. Implémenter cet algorithme en python.

   3. Faire un test avec 'Hermione'. Vous devez obtenir les 7 voisins suivants : [{'nom': 'Cormac', 'Courage': 9, 'Loyauté': 6, 'sagesse': 5, 'malice': 4, 'maison': 'Gryffondor'}, {'nom': 'Milicent', 'Courage': 9, 'Loyauté': 3, 'sagesse': 5, 'malice': 6, 'maison': 'Serpentar'}, {'nom': 'Neville', 'Courage': 10, 'Loyauté': 5, 'Sagesse': 6, 'Malice': 4, 'Maison': 'Gryffondor'}, {'nom': 'Padma', 'Courage': 6, 'Loyauté': 6, 'Sagesse': 6, 'Malice': 9, 'Maison': 'Serdaigle'}, {'nom': 'Susan', 'Courage': 5, 'loyauté': 6, 'Sagesse': 5, 'malice': 5, 'Maison': 'Poufsouffle'}, {'nom': 'Angelina', 'Courage': 10, 'loyauté': 6, 'Sagesse': 5, 'Malice': 9, 'Maison': 'Gryffondor'}, {'nom': 'Colin', 'Courage': 10, 'Loyauté': 7, 'Sagesse': 4, 'Malice': 7, 'Maison': 'Gryffondor'}]

      La maison attribuée pour 'Hermione' est 'Gryffondor'.

   Code de déblocage de la correction :

5. Attribuer une maison

   On dispose d'une table et de cette nouvelle élève Niue qui n'a pas encore de maison. On sait que cette élève est de "Courage" de niveau 7, de "Loyauté" de niveau 8, 5 en niveau de "Sagesse" et 4 en niveau de "Malice".
   On cherche désormais à lui attribuer une maison.

   Implémenter en python l'algorithme de l'attribution :

   1. Trouver dans la table les 7 plus proches voisins de cette nouvelle élève.

   2. Parmi ces proches voisins, trouver la maison majoritaire.

   3. Renvoyer la maison majoritaire pour cette élève "Niue".

   Faire un test avec 'Hermione'. Vous devez obtenir comme maison "Gryffondor".